﻿#pragma once

#include<iostream>
#include<stdlib.h>

// Definition for a Node.
class Node 
{
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) 
    {
        val = _val;
        next = NULL;
        random = NULL;
    }
};

class Answer {
public:
    Node* copyRandomList(Node* head) {
        // 1.拷贝链表，并插入到原节点的后面
        Node* cur = head;
        while (cur)
        {
            Node* next = cur->next;

            Node* copy = (Node*)malloc(sizeof(Node));
            copy->val = cur->val;

            // 插入
            cur->next = copy;
            copy->next = next;

            // 迭代往下走
            cur = next;
        }

        // 2.置拷贝节点的random
        cur = head;
        while (cur)
        {
            Node* copy = cur->next;
            if (cur->random != NULL)
                copy->random = cur->random->next;
            else
                copy->random = NULL;

            cur = copy->next;
        }

        // 3.解拷贝节点，链接拷贝节点
        Node* copyHead = NULL, * copyTail = NULL;
        cur = head;
        while (cur)
        {
            Node* copy = cur->next;
            Node* next = copy->next;

            // copy解下来尾插
            if (copyTail == NULL)
            {
                copyHead = copyTail = copy;
            }
            else
            {
                copyTail->next = copy;
                copyTail = copy;
            }

            cur->next = next;

            cur = next;
        }

        return copyHead;
    }
};

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
   
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/
class error
{
public:
    Node* copyRandomList(Node* head)
    {
        if (head == nullptr)
            return nullptr;
        Node* head1 = head, * tail1 = head1->next;
        Node* tmp = nullptr;
        while (head1 != nullptr)
        {
            tmp = new Node(head1->val);
            head1->next = tmp;
            tmp->random = head1->random;
            tmp->next = tail1;
            head1->next = tail1;
            head1 = tail1;
            if (tail1)
                tail1 = tail1->next;
        }

        head1 = head, tail1 = head->next;
        while (tail1)
        {
            if (tail1->random != nullptr)
            {
                tail1->random = tail1->random->next;
            }
            else
            {
                tail1->random = nullptr;
            }
            if (tail1->next == nullptr)
                break;
            tail1 = tail1->next->next;
        }

        head1 = head;
        Node* copyhead = nullptr, * copytail = nullptr;
        while (head1 != nullptr)
        {
            if (copyhead == nullptr)
            {
                copytail = copyhead = head1->next;
                head1->next = head1->next->next;
            }
            else
            {
                copytail->next = head1->next;
                head1->next = head1->next->next;
                copytail = copytail->next;
            }
            head1 = head1->next;
        }
        copytail->next = nullptr;
        return copyhead;
    }
};

/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     struct Node *next;
 *     struct Node *random;
 * };
 */

struct Node* copyRandomList(struct Node* head)
{
    if (head == NULL)//判空
    {
        return NULL;
    }

    struct Node* cur = head;
    struct Node* add = NULL;

    while (cur)//复制节点在原结点后
    {
        add = (struct Node*)malloc(sizeof(struct Node));
        add->val = cur->val;
        add->next = cur->next;
        add->random = cur->random;
        cur->next = add;
        cur = cur->next->next;
    }

    cur = head;
    struct Node* copy = head->next;

    while (copy)//复制在复制链表random指针
    {
        if (copy->random)
        {
            copy->random = copy->random->next;
        }
        else
        {
            copy->random = NULL;
        }
        if (copy->next)
            copy = copy->next->next;
        else
            break;
    }

    struct Node* head1 = head->next;
    cur = head;

    copy = head1;

    while (copy)//连接好复制节点并恢复原节点
    {
        cur->next = cur->next->next;
        cur = cur->next;
        if (cur)
        {
            copy->next = cur->next;
            copy = copy->next;
        }
        else
        {
            copy->next = NULL;
            break;
        }
    }

    return head1;
}